ESTIMATION OF ALGORITHMS FOR CALCULATION OF DISTANCE BETWEEN DNA LINES

Mel'nikov Boris Feliksovich, Doctor of physical and mathematical sciences, professor, sub-department
of applied mathematics and informatics, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), barmaley62@yandex.ru
Pivneva Svetlana Valentpnovna, Candidate of pedagogical sciences, associate professor, sub-department of mathematical modeling, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), tlt.swetlana@rambler.ru
Trifonov Maksim Andreevich, Postgraduate student, Togliatti State University (14 Belorusskaya street, Togliatti, Russia), trifonov_max@mail.ru

621.317.7

Background. Often it is required to measure distinction or distance between two lines (for example, in evolutionary, structural or functional researches of biological lines). As line sequences of mitochondrial DNA approximately make 17 000 symbols {a, g, c, t}, in order to solve the set problem the authors chose objective
algorithms of indistinct comparison that calculate the distance in polynomial time. In the research, when calculating the metrics of the known algorithms of inexact comparison of lines, there were received various results. The work purpose is to develop the methods of qualitative assessment of the received results. Development of qualitative assessment will allow to choose the most acceptable algorithm that will improve researches in various subject areas.
Materials and methods. The theory of triangular norm in metric space was used as a method of research.
Results. The initial data were obtained from the NCBI databank, and 30 line sequences of mitochondrial DNA were randomly chosen. As a result of perfomance of algorithms of comparison of 30 line sequences the authors adduced qualitative estimates.
Conclusions. Using the obtained qualitative estimates of metrics the best algorithm of comparison of line sequences has been determined.

metric evaluation, algorithms, multiheuristic approach.

1. Gasfild D. Stroki, derev'ya i posledovatel'nosti v algoritmakh. Informatika i vychislitel'naya biologiya [Lines, trees and sequences in algorithms. Informatics and calculus biology]. Saint-Petersburg: Nevskiy dialekt, BKhV-Peterburg, 2003, 654 p.
2. Boytsov L. Prikladnaya matematika i informatika [Applied mathematics and informatics]. 2000, no. 7.
3. Mel'nikov B. F., Panin A. G. Vektor nauki Tol'yattinskogo gosudarstvennogo universiteta [Scientific vector of Togliatti State University]. 2012, no. 4 (22), pp. 83–86.
4. NCBI: nucleotide database, 2015. Available at: http://www.ncbi.nlm.nih.gov/nuccore.
5. Pivneva S. V., Trifonov M. A. Vektor nauki Tol'yattinskogo gosudarstvennogo universiteta [Scientific vector of Togliatti State University]. 2010, no. 3, pp. 28–30.
6. Mel'nikov B. F., Mel'nikova E. A. Izvestiya vysshikh uchebnykh zavedeniy. Povolzhskiy region. Ser. Estestvennye nauki [University proceedings. Volga region. Physical and mathematical sciences]. 2007, no. 2, pp. 25–28.
7. Sayfullina E. F., Semenov R. I. Evristicheskie algoritmy i raspredelennye vychisleniya [Heuristic algorithm and distributed calculations]. 2014, vol. 1, no. 2, pp. 43–57.
8. Needleman S., Wunsch C. Journal of Molecular Biology. 1970, no. 48 (3), pp. 443–453.
9. Winkler W. Proceedings of the Section on Survey Research Methods. American Statistical Association, 1990, pp. 354–359.
10. Ewing B., Hillier L., Wendl M., Green R. Genome Res. 1998, no. 8 (3), pp. 175–185.
11. Altschul S. F. Journal of Molecular Biology. 1991, no. 219 (3), pp. 555–565.